import BTree as BT
from mock import Mock
import unittest

#class TestBTree(unittest.TestCase):
#    
#    def setUp(self):
#        self.BTree = BT.BTree()
#        for i in xrange(100000):
#            self.BTree.Insert(i)
#
#    
#    def testSearch(self):
#        for i in xrange(100000,2):
#            self.assertTrue(self.BTree.Search(i))
#        
#    
#    def testDeletion(self):
#        for i in xrange(1,100000,2):
#            self.BTree.Delete(i)
        


class TestTwoThreeNode(unittest.TestCase):
    
    #Represents a two three tree created from inserts from 1 to 21
    bigTreeVerify = [[8],            #Root*
                     [[4],           #Root-Left
                         [[2],       #Root-Left-Left
                             [[1]],  #Root-Left-Left-Left
                             [[3]]   #Root-Left-Left-Middle
                         ],
                         [[6],       #Root-Left-Middle
                             [[5]],  #Root-Left-Middle-Left
                             [[7]]   #Root-Left-Middle-Middle
                         ]
                      ],
                      [[12,16],      #Root-Middle
                          [[10],     #Root-Middle-Left
                              [[9]], #Root-Middle-Left-Left
                              [[11]] #Root-Middle-Left-Middle
                          ],
                          [[14],     #Root-Middle-Middle
                              [[13]],#Root-Middle-Middle-Left
                              [[15]] #Root-Middle-Middle-Middle
                          ],
                          [[18,20],  #Root-Middle-Right
                              [[17]],#Root-Middle-Right-Left
                              [[19]],#Root-Middle-Right-Middle
                              [[21]] #Root-Middle-Right-Right
                          ]
                      ]
                 ]
    
    def createVerifyBigTree(self):
        Node = BT.TwoThreeNode(1)
        
        Inserts = range(2,22)
        
        for iCounter in Inserts:
            Node.Insert(iCounter)
        
        print "Node      : %s" % Node.Tree
        print "Verifying : %s" % self.bigTreeVerify
         
        self.verifyTree(Node,self.bigTreeVerify,["root"])
        
        return Node
    
    def verifyTree(self,Node,verify,path):
        print "Verifying : %s" % verify
        self.assertIsNotNone(Node, "Node unexpectedly None at path %s" % path)
        self.assertEquals(Node.Small,verify[0][0], "Node.Small == %s != %s at path %s " % (Node.Small,verify[0][0],path))        
        if(len(verify[0])==2):
            self.assertEquals(Node.Large,verify[0][1], "Node.Large == %s != %s at path %s " % (Node.Large,verify[0][1],path))
        else:
            self.assertIsNone(Node.Large, "Node.Large == %s != None at path %s " % (Node.Large,path))
            
        if(len(verify)>1):
            self.verifyTree(Node.Left,verify[1],path + ["l"])
            self.assertIsNotNone(Node.Left,"Left Node is None at path %s" % path)
            self.assertIs(Node.Left.Parent,Node, "Parent of the left node is not set correctly (Node.Left.Parent == %s != %s) at path %s" % (Node.Left.Parent, Node, path))
        else:
            self.assertIsNone(Node.Left,"Node.Left == %s != None at path %s " % (Node.Left,path))
        
        if(len(verify)>2):
            self.verifyTree(Node.Middle,verify[2],path + ["m"])
            self.assertIsNotNone(Node.Middle,"Middle Node is None at path %s" % path)
            self.assertIs(Node.Middle.Parent,Node, "Parent of the middle node is not set correctly (Node.Middle.Parent == %s != %s) at path %s" % (Node.Middle.Parent, Node, path))
        else:
            self.assertIsNone(Node.Middle,"Node.Middle == %s != None at path %s " % (Node.Middle,path))
        
        if(len(verify)>3):
            self.verifyTree(Node.Right,verify[3],path + ["r"])
            self.assertIsNotNone(Node.Right,"Right Node is None at path %s" % path)
            self.assertIs(Node.Right.Parent,Node, "Parent of the right node is not set correctly (Node.Right.Parent == %s != %s) at path %s" % (Node.Right.Parent, Node, path))
        else:
            self.assertIsNone(Node.Right,"Node.Right == %s != None at path %s " % (Node.Right,path))
    
    
    def testInserts(self):
        
        print "TestInserts"
        
        Inserts = [1,2,-1,-2,3,4,7,5,6,-3]
        
        Verifies =  [
                    [[0,1]],      #Root* Insert 1
                    [[1],         #Root* Insert 2
                       [[0]],     #Root-Left
                       [[2]]      #Root-Middle
                    ],
                    [[1],         #Root* Insert -1
                       [[-1,0]],  #Root-Left
                       [[2]]      #Root-Middle
                    ],
                    [[-1,1],      #Root* Insert -2
                       [[-2]],    #Root-Left
                       [[0]],     #Root-Middle
                       [[2]]      #Root-Right
                    ],
                    [[-1,1],      #Root* Insert 3
                       [[-2]],    #Root-Left
                       [[0]],     #Root-Middle
                       [[2,3]]    #Root-Right
                    ],
                    [[1],         #Root* Insert 4
                       [[-1],     #Root-Left
                        [[-2]],   #Root-Left-Left
                        [[-0]]    #Root-Left-Middle
                        ],    
                       [[3],      #Root-Middle
                        [[2]],    #Root-Middle-Left
                        [[4]]     #Root-Middle-Middle
                        ]
                    ],
                    [[1],         #Root* Insert 7
                       [[-1],     #Root-Left
                        [[-2]],   #Root-Left-Left
                        [[-0]]    #Root-Left-Middle
                        ],    
                       [[3],      #Root-Middle
                        [[2]],    #Root-Middle-Left
                        [[4,7]]   #Root-Middle-Middle
                        ]
                    ],
                    [[1],         #Root* Insert 5
                       [[-1],     #Root-Left
                        [[-2]],   #Root-Left-Left
                        [[-0]]    #Root-Left-Middle
                        ],    
                       [[3,5],    #Root-Middle
                        [[2]],    #Root-Middle-Left
                        [[4]],    #Root-Middle-Middle
                        [[7]]     #Root-Middle-Right
                        ]
                    ],
                    [[1],         #Root* Insert 6
                       [[-1],     #Root-Left
                        [[-2]],   #Root-Left-Left
                        [[-0]]    #Root-Left-Middle
                        ],    
                       [[3,5],    #Root-Middle
                        [[2]],    #Root-Middle-Left
                        [[4]],    #Root-Middle-Middle
                        [[6,7]]   #Root-Middle-Right
                        ]
                    ],
                    [[1],         #Root* Insert -3
                       [[-1],     #Root-Left
                        [[-3,-2]],   #Root-Left-Left
                        [[-0]]    #Root-Left-Middle
                        ],    
                       [[3,5],    #Root-Middle
                        [[2]],    #Root-Middle-Left
                        [[4]],    #Root-Middle-Middle
                        [[6,7]]   #Root-Middle-Right
                        ]
                    ]
                    ]
        
        Node = BT.TwoThreeNode(0)
        verify = [[0]]
        
        self.verifyTree(Node,verify,["root"])

        for iCounter in range(0,len(Inserts)):
            print "Inserting: %s" % Inserts[iCounter]
            Node.Insert(Inserts[iCounter])
            print "Tree is: %s" % Node.Tree
            self.verifyTree(Node,Verifies[iCounter],["root"])
    
        self.createVerifyBigTree()
    
    def testDelete(self):
        BigTree = self.createVerifyBigTree()
        
        verifyBigTree = self.bigTreeVerify[:] #create a copy

        #Delete 10
        subTree      = [[16],
                          [[12,14],
                            [[9,11]],
                            [[13]],
                            [[15]]
                           ],
                          [[18,20],
                           [[17]],
                           [[19]],
                           [[21]]
                           ]
                          ]

        verifyBigTree[2] = subTree
        
        
        print "Before delete(10) is:",BigTree.Tree
        BigTree.Delete(10)
        print "After delete(10) should be:", verifyBigTree
        print "After delete(10) is       :", BigTree.Tree
        self.verifyTree(BigTree,verifyBigTree,["big tree"])
        
        #Delete 20
        subTree =  [[18],
                       [[17]],
                       [[19,21]]
                    ]

        verifyBigTree[2][2] = subTree
        
        print "Before delete(20) is:",BigTree.Tree
        BigTree.Delete(20)
        print "After delete(20) should be:", verifyBigTree
        print "After delete(20) is       :", BigTree.Tree
        self.verifyTree(BigTree,verifyBigTree,["big tree"])
        
        # Delete 17
        subTree =  [[19],
                       [[18]],
                       [[21]]
                    ]
       
        print "Before delete(17) is:",BigTree.Tree
        verifyBigTree[2][2] = subTree
        BigTree.Delete(17)
        print "After delete(17) should be:", verifyBigTree
        print "After delete(17) is       :", BigTree.Tree
        self.verifyTree(BigTree,verifyBigTree,["big tree"])
        
        #Delete 18
        subTree      = [[14],
                          [[12],
                            [[9,11]],
                            [[13]]
                           ],
                          [[16],
                           [[15]],
                           [[19,21]]
                           ]
                          ]
        
        
        verifyBigTree[2] = subTree
        print "Before delete(18) is:",BigTree.Tree
        BigTree.Delete(18)
        print "After delete(17) should be:", verifyBigTree
        print "After delete(17) is       :", BigTree.Tree
        self.verifyTree(BigTree,verifyBigTree,["big tree"])
    
    def testSplitAttachCase0(self):
        ParentNode = Mock(BT.TwoThreeNode) # Create a parent node
        
        RealNode = BT.TwoThreeNode(2) #Root of the tree
        
        self.verifyTree(RealNode,[[2]],["RealNode"])
        
        RealNode.Parent = ParentNode
        RealNode.Insert(1)
        self.verifyTree(RealNode,[[1,2]],["RealNode"])
        
        #Test that attach is called
        RealNode.Insert(3)          # Should Trigger a split and attach method call to the parent
        
        CallArgs = ParentNode.Attach.call_args
        
        self.assertIsInstance(CallArgs[0][0],BT.TwoThreeNode)
        
        self.verifyTree(CallArgs[0][0],[[1]],"left parameter")
        
        self.assertEqual(CallArgs[0][1],2, "Middle value is not 2.")
        
        self.assertIsInstance(CallArgs[0][2],BT.TwoThreeNode)
        
        self.verifyTree(CallArgs[0][2],[[3]],"right parameter")
    
    def testSplitAttachCase1A(self):
        
        verifyTree = [[4,10],[[2]],[[6]],[[15]]]
        
        A = BT.TwoThreeNode(2)
        B = BT.TwoThreeNode(6)
        C = BT.TwoThreeNode(15)
        
        Root = BT.TwoThreeNode(10)
        
        Root.Middle = C
        
        Root.Attach(A,4,B)
        
        self.verifyTree(Root, verifyTree, ["root"])
        self.assertIs(Root.Left,A)
        self.assertIs(Root.Middle,B)
        self.assertIs(Root.Right,C)
    
    def testSplitAttach1B(self):
        verifyTree = [[10,20],[[5]],[[15]],[[25]]]
         
        Root = BT.TwoThreeNode(10)
        
        A = BT.TwoThreeNode(5)
        B = BT.TwoThreeNode(15)
        C = BT.TwoThreeNode(25)
         
        Root.Left = A
        Root.Attach(B,20,C)
         
        self.verifyTree(Root, verifyTree, ["root"])
        self.assertIs(Root.Left,A)
        self.assertIs(Root.Middle,B)
        self.assertIs(Root.Right,C)
        
    def testSplitAttachCase2A(self):
        verifyLeftTree  = [[10],[[5]],[[15]]]
        verifyRightTree = [[25],[[22]],[[30]]]
        
        Root = BT.TwoThreeNode(20)
        Root.Large = 25
        
        A = BT.TwoThreeNode(5)
        B = BT.TwoThreeNode(15)
        C = BT.TwoThreeNode(22)
        D = BT.TwoThreeNode(30)
        
        MockParent = Mock(BT.TwoThreeNode)
        
        Root.Parent = MockParent
        Root.Left     = Mock(BT.TwoThreeNode)
        Root.Middle   = C
        Root.Right    = D
        
        Root.Attach(A,10,B)
        
        CallArgs = MockParent.Attach.call_args
        
        self.assertTrue(MockParent.Attach.called, "Parent attach method was not called.")
        
        LeftBranch = CallArgs[0][0]
        MiddleValue = CallArgs[0][1]
        RightBranch = CallArgs[0][2]
        
        self.verifyTree(LeftBranch, verifyLeftTree, ["left root"])
        self.verifyTree(RightBranch, verifyRightTree, ["right root"])
        self.assertEqual(20,MiddleValue)
        
        self.assertIs(LeftBranch.Left,A)
        self.assertIs(LeftBranch.Middle,B)
        
        self.assertIs(RightBranch.Left,C)
        self.assertIs(RightBranch.Middle,D)
        
    def testSplitAttachCase2B(self):
        verifyLeftTree  = [[10],[[5]],[[15]]]
        verifyRightTree = [[25],[[22]],[[30]]]
        
        Root = BT.TwoThreeNode(10)
        Root.Large = 25
        
        A = BT.TwoThreeNode(5)
        B = BT.TwoThreeNode(15)
        C = BT.TwoThreeNode(22)
        D = BT.TwoThreeNode(30)
        
        MockParent = Mock(BT.TwoThreeNode)
        
        Root.Parent = MockParent
        Root.Left     = A 
        Root.Middle   = Mock(BT.TwoThreeNode)
        Root.Right    = D
        
        Root.Attach(B,20,C)
        
        CallArgs = MockParent.Attach.call_args
        
        self.assertTrue(MockParent.Attach.called, "Parent attach method was not called.")
        
        LeftBranch  = CallArgs[0][0]
        MiddleValue = CallArgs[0][1]
        RightBranch = CallArgs[0][2]
        
        self.verifyTree(LeftBranch, verifyLeftTree, ["left root"])
        self.verifyTree(RightBranch, verifyRightTree, ["right root"])
        self.assertEqual(20,MiddleValue)
        
        self.assertIs(LeftBranch.Left,  A)
        self.assertIs(LeftBranch.Middle,B)
        
        self.assertIs(RightBranch.Left,C)
        self.assertIs(RightBranch.Middle,D)
    
    def testSplitAttachCase2C(self):
        verifyLeftTree  = [[10],[[5]],[[15]]]
        verifyRightTree = [[25],[[22]],[[30]]]
        
        Root = BT.TwoThreeNode(10)
        Root.Large = 20
        
        A = BT.TwoThreeNode(5)
        B = BT.TwoThreeNode(15)
        C = BT.TwoThreeNode(22)
        D = BT.TwoThreeNode(30)
        
        MockParent = Mock(BT.TwoThreeNode)
        
        Root.Parent = MockParent
        Root.Left     = A 
        Root.Middle   = B
        Root.Right    = Mock(BT.TwoThreeNode)
        
        Root.Attach(C,25,D)
        
        CallArgs = MockParent.Attach.call_args
        
        self.assertTrue(MockParent.Attach.called, "Parent attach method was not called.")
        
        LeftBranch  = CallArgs[0][0]
        MiddleValue = CallArgs[0][1]
        RightBranch = CallArgs[0][2]
        
        self.verifyTree(LeftBranch, verifyLeftTree, ["left root"])
        self.verifyTree(RightBranch, verifyRightTree, ["right root"])
        self.assertEqual(20,MiddleValue)
        
        self.assertIs(LeftBranch.Left,  A)
        self.assertIs(LeftBranch.Middle,B)
        
        self.assertIs(RightBranch.Left,C)
        self.assertIs(RightBranch.Middle,D)


    def verifyTreeCase3(self,Root,A,B,C,D):
        verifyTree = [[20],[[10],[[5]],[[15]]],[[25],[[22]],[[30]]]]
        
        self.verifyTree(Root, verifyTree, ["root"])
        
        self.assertIs(Root.Left.Left,A)
        self.assertIs(Root.Left.Middle,B)
        
        self.assertIs(Root.Middle.Left,C)
        self.assertIs(Root.Middle.Middle,D)

    def testSplitAttachCase3A(self):

        
        Root = BT.TwoThreeNode(20)
        Root.Large = 25
        
        A = BT.TwoThreeNode(5)
        B = BT.TwoThreeNode(15)
        C = BT.TwoThreeNode(22)
        D = BT.TwoThreeNode(30)
        
        Root.Left     = Mock(BT.TwoThreeNode)
        Root.Middle   = C
        Root.Right    = D
        
        Root.Attach(A,10,B)
        
        self.verifyTreeCase3(Root, A, B, C, D)
        

        
    def testSplitAttachCase3B(self):
        
        Root = BT.TwoThreeNode(10)
        Root.Large = 25
        
        A = BT.TwoThreeNode(5)
        B = BT.TwoThreeNode(15)
        C = BT.TwoThreeNode(22)
        D = BT.TwoThreeNode(30)
        
        Root.Left     = A 
        Root.Middle   = Mock(BT.TwoThreeNode)
        Root.Right    = D
        
        Root.Attach(B,20,C)
        
        self.verifyTreeCase3(Root, A, B, C, D)
    
    def testSplitAttachCase3C(self):
        
        Root = BT.TwoThreeNode(10)
        Root.Large = 20
        
        A = BT.TwoThreeNode(5)
        B = BT.TwoThreeNode(15)
        C = BT.TwoThreeNode(22)
        D = BT.TwoThreeNode(30)
        
        Root.Left     = A 
        Root.Middle   = B
        Root.Right    = Mock(BT.TwoThreeNode)
        
        Root.Attach(C,25,D)

        self.verifyTreeCase3(Root, A, B, C, D)
        
    def testSearch(self):
        Root = BT.TwoThreeNode(1)
        Inserts = range(2,22)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, self.bigTreeVerify, ["root"])
        
        print "Searching for root."
        self.assertIs(Root,                    Root.Search(8)[1],  "Search did not return correctly (8)")
        
        print "Searching for 14 node."
        found, Node = Root.Search(14)
        self.assertIs(Root.Middle.Middle,      Node, "Search did not return correctly (14) : (True, %s) != (%s,%s)" % (Root.Middle.Middle.Tree, found, Node.Tree))
        
        self.assertIs(Root.Middle.Right,       Root.Search(18)[1], "Search did not return correctly (18)")
        
        self.assertIs(Root.Middle.Right,       Root.Search(20)[1], "Search did not return correctly (20)")
        
        self.assertIs(Root.Middle.Left.Left,   Root.Search(9)[1],  "Search did not return correctly (9)")
        
        self.assertIs(Root.Middle.Right.Right, Root.Search(21)[1], "Search did not return correctly (21)")
        
        for iCounter in range(1,21):
            self.assertIsNotNone(Root.Search(iCounter)[1],"Search did not find %s correctly (returned None)." % iCounter)
        
        for iCounter in range(-21,0):
            self.assertFalse(Root.Search(iCounter)[0], "Search did not return false on integer %s" % iCounter)
            
        for iCounter in range(22,30):
            self.assertFalse(Root.Search(iCounter)[0], "Search did not return false on integer %s" % iCounter)
    
    def testSuccessor(self):
        Root = BT.TwoThreeNode(1)
        Inserts = range(2,22)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, self.bigTreeVerify, ["root"])
        
        node = Root.Successor(8)
        self.assertIs(node,Root.Middle.Left.Left, "In order successor node of Root(8) is not correct:\n%s\nvs.\n%s"%(node.Tree,Root.Middle.Left.Left.Tree))
        self.assertEqual(node.Small,9, "In order successor value %s!=9 of Root(8) is not correct." % node.Small)
        
        node = Root.Successor(12)
        self.assertIs(node,Root.Middle.Middle.Left, "In order successor node of Root(8) is not correct.")
        self.assertEqual(node.Small,13, "In order successor value %s!=13 of Root(12) is not correct." % node.Small)

        node = Root.Successor(4)
        self.assertIs(node,Root.Left.Middle.Left, "In order successor node of Root(8) is not correct.")
        self.assertEqual(node.Small,5, "In order successor value %s !=5 of Root(4) is not correct."% node.Small)
        
    
    def testRedistributeLeaf2NodeCase1A(self):
        # 2 Node Case 1A
        
        Inserts = [3,4,2]
        
        smallTree = [[3],[[1,2]],[[4]]]        
        smallTreeRedistributed = [[2],[[1]],[[3]]]
        
        Root = BT.TwoThreeNode(1)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, smallTree, ["small tree"])
        Root.Middle.Small = None
        
        Root.Redistribute(Root.Middle)
        self.verifyTree(Root, smallTreeRedistributed, ["small redistributed tree"])
   
    def testRedistributeLeaf2NodeCase1B(self):
        # 2 Node Case 1B
        
        Inserts = [3,4,5]
        
        smallTree = [[3],[[2]],[[4,5]]]        
        smallTreeRedistributed = [[4],[[3]],[[5]]]
        
        Root = BT.TwoThreeNode(2)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, smallTree, ["small tree"])
        Root.Left.Small = None
        
        Root.Redistribute(Root.Left)
        self.verifyTree(Root, smallTreeRedistributed, ["small redistributed tree"])     

    def testRedistributeLeaf2NodeCase2A(self):
        # 2 Node Case 2A
        
        Parent = Mock(BT.TwoThreeNode)
        
        Inserts = [3,4]
        
        smallTree = [[3],[[1]],[[4]]]        
        smallTreeRedistributed = [[1,3]]
        
        Node = BT.TwoThreeNode(1)
        
        for iCounter in Inserts:
            Node.Insert(iCounter)
        
        self.verifyTree(Node, smallTree, ["small tree"])
        Node.Middle.Small = None
        
        Node.Parent = Parent
        
        Node.Redistribute(Node.Middle)
        self.verifyTree(Node, smallTreeRedistributed, ["small redistributed tree"])

        self.assertTrue(Parent.Merge.called)

        MergeCallArgs = Parent.Merge.call_args
        
        self.assertIsNotNone(MergeCallArgs, "Redistribute method did not trigger a merge.")
        self.assertEqual(MergeCallArgs[0][0], Node, "Redistribute did not call merge with the correct parameters.")

    def testRedistributeLeaf2NodeCase2B(self):
        # 2 Node Case 2B
        
        Parent = Mock(BT.TwoThreeNode)
        
        Inserts = [3,4]
        
        smallTree = [[3],[[2]],[[4]]]        
        smallTreeRedistributed = [[3,4]]
        
        Node = BT.TwoThreeNode(2)
        
        for iCounter in Inserts:
            Node.Insert(iCounter)
        
        self.verifyTree(Node, smallTree, ["small tree"])
        Node.Left.Small = None
        
        Node.Parent = Parent
        
        Node.Redistribute(Node.Left)
        self.verifyTree(Node, smallTreeRedistributed, ["small redistributed tree"])

        self.assertTrue(Parent.Merge.called)

        MergeCallArgs = Parent.Merge.call_args
        
        self.assertIsNotNone(MergeCallArgs, "Redistribute method did not trigger a merge.")
        self.assertEqual(MergeCallArgs[0][0], Node, "Redistribute did not call merge with the correct parameters.")

    def testRedistributeLeaf3NodeCase1A(self):
        # 3 Root Case 1A
        
        Inserts = [9,10,30,40,20]
        
        Tree = [[9,30],[[8]],[[10,20]],[[40]]]        
        TreeRedistributed = [[9,20],[[8]],[[10]],[[30]]]
        
        Root = BT.TwoThreeNode(8)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, Tree, ["tree"])
        Root.Right.Small = None
        
        Root.Redistribute(Root.Right)
        print "Root Redistributed:",Root.Tree
        self.verifyTree(Root, TreeRedistributed, ["redistributed tree"])

    def testRedistributeLeaf3NodeCase1B(self):
        # 3 Root Case 1B
        
        Inserts = [9,10,30,40,50]
        
        Tree = [[9,30],[[8]],[[10]],[[40,50]]]        
        TreeRedistributed = [[9,40],[[8]],[[30]],[[50]]]
        
        Root = BT.TwoThreeNode(8)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, Tree, ["tree"])
        Root.Middle.Small = None
        
        Root.Redistribute(Root.Middle)
        print "Redistributed Tree: ", Root.Tree
        self.verifyTree(Root, TreeRedistributed, ["redistributed tree"])

    def testRedistributeLeaf3NodeCase1C(self):
        # 3 Root Case 1C
        
        Inserts = [9,10,30,40,20]
        
        Tree = [[9,30],[[8]],[[10,20]],[[40]]]        
        TreeRedistributed = [[10,30],[[9]],[[20]],[[40]]]
        
        Root = BT.TwoThreeNode(8)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, Tree, ["tree"])
        Root.Left.Small = None
        
        Root.Redistribute(Root.Left)
        self.verifyTree(Root, TreeRedistributed, ["redistributed tree"])

    def testRedistributeLeaf3NodeCase2A(self):
        # 3 Root Case 2A
        
        Inserts = [9,20,30,40]
        
        Tree = [[9,30],[[8]],[[20]],[[40]]]        
        TreeRedistributed = [[9],[[8]],[[20,30]]]
        
        Root = BT.TwoThreeNode(8)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, Tree, ["tree"])
        Root.Right.Small = None
        
        Root.Redistribute(Root.Right)
        print "Redistributed Tree: ", Root.Tree
        self.verifyTree(Root, TreeRedistributed, ["redistributed tree"])

    def testRedistributeLeaf3NodeCase2B(self):
        # 3 Root Case 2B
        
        Inserts = [9,20,30,40]
        
        Tree = [[9,30],[[8]],[[20]],[[40]]]        
        TreeRedistributed = [[9],[[8]],[[30,40]]]
        
        Root = BT.TwoThreeNode(8)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, Tree, ["tree"])
        Root.Middle.Small = None
        
        Root.Redistribute(Root.Middle)
        print "Redistributed Tree: ", Root.Tree
        self.verifyTree(Root, TreeRedistributed, ["redistributed tree"])

    def testRedistributeLeaf3NodeCase2C(self):
        # 3 Root Case 2C
        
        Inserts = [9,20,30,40]
        
        Tree = [[9,30],[[8]],[[20]],[[40]]]        
        TreeRedistributed = [[30],[[9,20]],[[40]]]
        
        Root = BT.TwoThreeNode(8)
        
        for iCounter in Inserts:
            Root.Insert(iCounter)
        
        self.verifyTree(Root, Tree, ["tree"])
        Root.Left.Small = None
        RootRight = Root.Right
        
        Root.Redistribute(Root.Left)
        self.verifyTree(Root, TreeRedistributed, ["redistributed tree"])
        
        self.assertIs(Root.Middle,RootRight, "The right node was not moved to the middle node after redistribution.")
        
    def testMergeInternal3NodeCase1A(self):
        # 3 Root Case 1A
                
        TreeMerged = [[10],         #Root
                          [[5],      #Root-Left
                             [[1]], #Root-Left-Left
                             [[6]] #Root-Left-Middle
                           ],
                           [[15,20],#Root-Middle
                             [[12]],#Root-Middle-Left
                             [[16]],#Root-Middle-Middle
                             [[25]] #Root-Middle-Right
                            ]
                      ]
        
        # Manually create connections
        Root               = BT.TwoThreeNode(10)
        Root.Large         = 20
        Root.Left          = BT.TwoThreeNode(5)
        Root.Left.Left     = BT.TwoThreeNode(1)
        Root.Left.Middle   = BT.TwoThreeNode(6)
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Left   = BT.TwoThreeNode(12)
        Root.Middle.Middle = BT.TwoThreeNode(16)
        Root.Right         = BT.TwoThreeNode(25)
        
        A = Root.Left
        B = Root.Middle.Left
        C = Root.Middle.Middle
        D = Root.Right
        
        Root.Merge(Root.Right)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left,          A)
        self.assertIs(Root.Middle.Left,   B)
        self.assertIs(Root.Middle.Middle, C)
        self.assertIs(Root.Middle.Right,  D)
        
    def testMergeInternal3NodeCase1B(self):
        # 3 Root Case 1B
                
        TreeMerged = [[10,17],      #Root
                          [[5],      #Root-Left
                             [[1]], #Root-Left-Left
                             [[6]]  #Root-Left-Middle
                           ],
                           [[15],   #Root-Middle
                             [[14]],#Root-Middle-Left
                             [[16]] #Root-Middle-Middle
                            ],
                           [[20],   #Root-Right
                             [[18]],#Root-Right-Left
                             [[25]] #Root-Right-Middle
                            ]                      
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Large         = 20
        Root.Left          = BT.TwoThreeNode(5)
        Root.Left.Left     = BT.TwoThreeNode(1)
        Root.Left.Middle   = BT.TwoThreeNode(6)
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Large  = 17
        Root.Middle.Left   = BT.TwoThreeNode(14)
        Root.Middle.Middle = BT.TwoThreeNode(16)
        Root.Middle.Right  = BT.TwoThreeNode(18)
        Root.Right         = BT.TwoThreeNode(25)
        
        A = Root.Left
        B = Root.Middle.Left
        C = Root.Middle.Middle
        D = Root.Middle.Right
        E = Root.Right
        
        Root.Merge(Root.Right)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left,         A)
        self.assertIs(Root.Middle.Left,  B)
        self.assertIs(Root.Middle.Middle,C)
        self.assertIs(Root.Right.Left,   D)
        self.assertIs(Root.Right.Middle, E)


    def testMergeInternal3NodeCase2A(self):
        # 3 Root Case 2A
                
        TreeMerged = [[10],      #Root
                          [[5],      #Root-Left
                             [[1]], #Root-Left-Left
                             [[6]] #Root-Left-Middle
                           ],
                           [[20,25], #Root-Middle
                             [[15]], #Root-Middle-Left
                             [[22]], #Root-Middle-Middle
                             [[28]]  #Root-Middle-Right
                            ]                      
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Large         = 20
        Root.Left          = BT.TwoThreeNode(5)
        Root.Left.Left     = BT.TwoThreeNode(1)
        Root.Left.Middle   = BT.TwoThreeNode(6)
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Right         = BT.TwoThreeNode(25)
        Root.Right.Left    = BT.TwoThreeNode(22)
        Root.Right.Middle  = BT.TwoThreeNode(28)
        
        A = Root.Left
        B = Root.Middle
        C = Root.Right.Left
        D = Root.Right.Middle
        
        
        Root.Merge(Root.Middle)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left,         A)
        self.assertIs(Root.Middle.Left,  B)
        self.assertIs(Root.Middle.Middle,C)
        self.assertIs(Root.Middle.Right, D)

    def testMergeInternal3NodeCase2B(self):
        # 3 Root Case 2B
                
        TreeMerged = [[10,25],      #Root
                          [[5],     #Root-Left
                             [[1]], #Root-Left-Left
                             [[6]]  #Root-Left-Middle
                           ],
                           [[20],    #Root-Middle
                             [[15]], #Root-Middle-Left
                             [[22]]  #Root-Middle-Middle
                            ],                      
                           [[30],    #Root-Middle
                             [[28]], #Root-Middle-Left
                             [[32]]  #Root-Middle-Middle
                            ]
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Large         = 20
        Root.Left          = BT.TwoThreeNode(5)
        Root.Left.Left     = BT.TwoThreeNode(1)
        Root.Left.Middle   = BT.TwoThreeNode(6)
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Right         = BT.TwoThreeNode(25)
        Root.Right.Large   = 30
        Root.Right.Left    = BT.TwoThreeNode(22)
        Root.Right.Middle  = BT.TwoThreeNode(28)
        Root.Right.Right   = BT.TwoThreeNode(32)
        
        A = Root.Left
        B = Root.Middle
        C = Root.Right.Left
        D = Root.Right.Middle
        E = Root.Right.Right
        
        Root.Merge(Root.Middle)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left,         A)
        self.assertIs(Root.Middle.Left,  B)
        self.assertIs(Root.Middle.Middle,C)
        self.assertIs(Root.Right.Left,   D)
        self.assertIs(Root.Right.Middle, E)

    def testMergeInternal3NodeCase3A(self):
        # 3 Root Case 3A
                
        TreeMerged = [[20],         #Root
                          [[10,15], #Root-Left
                             [[1,5]], #Root-Left-Left
                             [[12]],  #Root-Left-Middle
                             [[18]]   #Root-Left-Right
                           ],
                           [[25],    #Root-Middle
                             [[22]], #Root-Middle-Left
                             [[28]]  #Root-Middle-Middle
                            ]
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Large         = 20
        Root.Left          = BT.TwoThreeNode(1)
        Root.Left.Large    = 5
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Left   = BT.TwoThreeNode(12)
        Root.Middle.Middle = BT.TwoThreeNode(18)
        Root.Right         = BT.TwoThreeNode(25)
        Root.Right.Left    = BT.TwoThreeNode(22)
        Root.Right.Middle  = BT.TwoThreeNode(28)
        
        A = Root.Left
        B = Root.Middle.Left
        C = Root.Middle.Middle
        D = Root.Right
        
        
        Root.Merge(Root.Left)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left.Left,    A)
        self.assertIs(Root.Left.Middle,  B)
        self.assertIs(Root.Left.Right,   C)
        self.assertIs(Root.Middle,       D)
        

    def testMergeInternal3NodeCase3B(self):
        # 3 Root Case 3B
                
        TreeMerged = [[15,20],         #Root
                          [[10], #Root-Left
                             [[1,5]], #Root-Left-Left
                             [[12]]  #Root-Left-Middle
                           ],
                          [[18], #Root-Middle
                             [[16]], #Root-Middle-Left
                             [[19]]  #Root-Middle-Right
                           ],
                           [[25],    #Root-Right
                             [[22]], #Root-Right-Left
                             [[28]]  #Root-Right-Middle
                            ]
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Large         = 20
        Root.Left          = BT.TwoThreeNode(1)
        Root.Left.Large    = 5
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Large  = 18
        Root.Middle.Left   = BT.TwoThreeNode(12)
        Root.Middle.Middle = BT.TwoThreeNode(16)
        Root.Middle.Right  = BT.TwoThreeNode(19)
        Root.Right         = BT.TwoThreeNode(25)
        Root.Right.Left    = BT.TwoThreeNode(22)
        Root.Right.Middle  = BT.TwoThreeNode(28)
        
        A = Root.Left
        B = Root.Middle.Left
        C = Root.Middle.Middle
        D = Root.Middle.Right
        E = Root.Right
        
        
        Root.Merge(Root.Left)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left.Left,     A)
        self.assertIs(Root.Left.Middle,   B)
        self.assertIs(Root.Middle.Left,   C)
        self.assertIs(Root.Middle.Middle, D)
        self.assertIs(Root.Right,         E)
    
    def testMergeInternal2NodeCase1A(self):
        # 2 Node Case 1A
        
        MockParent = Mock(BT.TwoThreeNode)
                
        TreeMerged = [[5,10],   #Root
                          [[1]], #Root-Left
                          [[6]], #Root-Middle
                          [[15,20]]    #Root-Right
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Parent = MockParent
        Root.Left          = BT.TwoThreeNode(5)
        Root.Left.Left     = BT.TwoThreeNode(1)
        Root.Left.Middle   = BT.TwoThreeNode(6)
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Large  = 20
        
        A = Root.Left.Left
        B = Root.Left.Middle
        C = Root.Middle

        Root.Merge(Root.Middle)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left,    A)
        self.assertIs(Root.Middle,  B)
        self.assertIs(Root.Right,   C)
        
        MockParent.Merge.assert_called_with(Root)

    def testMergeInternal2NodeCase1B(self):
        # 2 Node Case 1B
        
        MockParent = Mock(BT.TwoThreeNode)
                
        TreeMerged = [[10,15],   #Root
                          [[1,5]], #Root-Left
                          [[12]],  #Root-Middle
                          [[20]]   #Root-Right
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Parent = MockParent
        Root.Left          = BT.TwoThreeNode(1)
        Root.Left.Large    = 5
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Left   = BT.TwoThreeNode(12)
        Root.Middle.Middle  = BT.TwoThreeNode(20)
        
        A = Root.Left
        B = Root.Middle.Left
        C = Root.Middle.Middle

        Root.Merge(Root.Left)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left,    A)
        self.assertIs(Root.Middle,  B)
        self.assertIs(Root.Right,   C)

        MockParent.Merge.assert_called_with(Root)
        
    def testMergeInternal2NodeCase2A(self):
        # 2 Node Case 2A
        
                 
        TreeMerged = [[8],     #Root
                          [[5],     #Root-Left
                             [[1]], #Root-Left-Left
                             [[6]]  #Root-Left-Middle
                           ],
                          [[10],       #Root-Middle
                             [[9]],    #Root-Middle-Left
                             [[15,20]] #Root-Middle-Right
                           ]
                      ]
        
        # Manually create connections
        Root               = BT.TwoThreeNode(10)
        Root.Left          = BT.TwoThreeNode(5)
        Root.Left.Large    = 8
        Root.Left.Left     = BT.TwoThreeNode(1)
        Root.Left.Middle   = BT.TwoThreeNode(6)
        Root.Left.Right    = BT.TwoThreeNode(9)
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Large  = 20
        
        A = Root.Left.Left
        B = Root.Left.Middle
        C = Root.Left.Right
        D = Root.Middle

        Root.Merge(Root.Middle)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left.Left,    A)
        self.assertIs(Root.Left.Middle,  B)
        self.assertIs(Root.Middle.Left,  C)
        self.assertIs(Root.Middle.Middle,D)

    def testMergeInternal2NodeCase2B(self):
        # 2 Node Case 2B
                 
        TreeMerged = [[15],     #Root
                          [[10],     #Root-Left
                             [[1,5]],#Root-Left-Left
                             [[12]]  #Root-Left-Middle
                           ],
                          [[20],     #Root-Middle
                             [[16]], #Root-Middle-Left
                             [[25]]  #Root-Middle-Right
                           ]
                      ]
        
        # Manually create connections
        Root = BT.TwoThreeNode(10)
        Root.Left          = BT.TwoThreeNode(1)
        Root.Left.Large    = 5
        Root.Middle        = BT.TwoThreeNode(15)
        Root.Middle.Large  = 20
        Root.Middle.Left   = BT.TwoThreeNode(12)
        Root.Middle.Middle = BT.TwoThreeNode(16)
        Root.Middle.Right  = BT.TwoThreeNode(25)
        
        A = Root.Left
        B = Root.Middle.Left
        C = Root.Middle.Middle
        D = Root.Middle.Right

        Root.Merge(Root.Left)
        
        self.verifyTree(Root, TreeMerged, ["root"])
        
        self.assertIs(Root.Left.Left,    A)
        self.assertIs(Root.Left.Middle,  B)
        self.assertIs(Root.Middle.Left,  C)
        self.assertIs(Root.Middle.Middle,D)

if __name__ == "main":
    unittest.main()
